# coding: utf-8
# 归并排序实现
# 图解：https://www.cnblogs.com/shierlou-123/p/11310040.html（先分后治）

#这里用python的分片可以减少代码
#slice s and slice t
def merge(s,t):
    #合并结果
    m=[]
    i=j=0
    lenS=len(s)
    lenT=len(t)
    while i<lenS and j<lenT:
        if s[i]<=t[j]:
            m.append(s[i])
            i+=1
        else:
            m.append(t[j])
            j+=1
    if j==lenT:
        for k in s[i:]:  #从i到末尾，真方便
            m.append(k)
    else:
        for k in t[j:]:
            m.append(k)
    return m

def mergeSort(lst):
    lstLen=len(lst)
    #单个元素的列表已经是有序的，直接返回
    if lstLen<=1:
        return lst
    mid=lstLen/2
    #拆分左边，[0,mid-1] end取不到
    left=mergeSort(lst[:mid])
    #拆分右边，[mid,len-1]
    right=mergeSort(lst[mid:])
    #治理（合并）
    return merge(left, right)


s1=[1,11,111,1111,3333,4444]
s2=[2,22,222,2222]
print(merge(s1,s2))

lst = [1,11,2,22,3,33,-1,2,3]
print("merge sort:",mergeSort(lst))
